//{=================================================================================
//! @file    d1.cpp
//! @date    2013-09-28 22:35
//! @author  Anton Samsonov <Fivapr...@inbox.ru>
//! @version 0.1
//!
//! @mainpage   Hello! This is documentation for control 2007.
//!             You'd better check warning.
//!
//! Program building table of "good binaries" with length from 1 to n.
//!
//! @par    Program gets a number n (0 <= n < 48).
//!         Build a table of numbers b(n, k), where b(n, k) - amount
//!         of binary words with length n and amount of units k.
//!         In each word 2 units must be divided by nills.
//!         (There can't be smth like ...11...)
//!
//!
//! @note   V0.1
//!         - Added OUT     (ifdef _EJC).
//!         - Added EJC_OUT (if _EJC is not defined)
//!         - Added ASSERT  (ifdef DEBUG).
//!         - Added comb (n, k)          function.
//!         - Added good_binaries (n, k) function
//!         - First aim of program is succeed
//!
//! @todo   - ...
//!
//! @warning  Keep calm and do science!
//}=================================================================================

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#ifdef _EJC
    #define OUT printf
    #define EJC_OUT if (0) printf
#else
    #define OUT if (0) printf
    #define EJC_OUT printf
#endif //!< Macro for ejudge system.
//----------------------------------------
#define DEBUG
//----------------------------------------

#ifdef DEBUG
    #define ASSERT( cond )                          \
    if (!(cond)) {                                  \
        fprintf (stderr, "# Assertion fail : %s. "  \
                        "File %s, line %d\n",       \
                        #cond, __FILE__, __LINE__); \
        abort();                                    \
    }
#else
    #define ASSERT( cond )
#endif //!< ASSERT is active only when DEBUG is defined.

int comb (int n, int k);

int good_binaries(int n, int k);

int main()
{
    OUT ("# This is %s. It's compiled %s %s by Anton Samsonov\n", __FILE__, __DATE__, __TIME__);

    int scanned = 0;
    OUT ("# Input a number you want to build table for.\n");
    int scanf_ret = scanf("%d", &scanned);
    if (scanf_ret < 1) { OUT ("# Input is not valid. You need to input positive decimal number.\n"); return 1; }

    if (scanned < 0) { OUT ("# Input is not valid. You need to input positive decimal number.\n"); return 1; }

    OUT ("# Here is table build for %d:\n", scanned);
    int i = 0, j = 0, temp = 0;
    for (i = 0; i <= scanned; i ++) {
        for (j = 0; j <= i; j ++) {
            temp = good_binaries (i, j);
            if (temp) printf("%d ", temp);
        }
        printf("\n");
    }

    return 0;
}

/**
    comb - combinatoric function: comb(n, k) = n! / (k! * (n - k)!
    where '!' is sign of factorial.

    @param    n    length of sequence.
    @param    k    amount of numbers in new sequence.

    @return        number of combiantions of n by k

    @note          n can't be less than k.
**/

int comb (int n, int k)
{
    ASSERT (n >= k);
    int temp = 1;

    k = (n - k < k)? (n - k) : k;

    int i = 0;
    for (i = k + 1; i <= n; i ++) temp *= i; // numerator
    for (i = 2; i <= n - k; i ++) temp /= i; // denomenator

    return temp;
}

/**
    good_binaries - finding amount of "good binaries": \
    with length n and amount of units k.

    @param    n    length of binary word
    @param    k    amount of units in binary word.

    @return        amount of good binaries.

    @note          We should check units are not nearby to each other.
                   So we change each 01 to 1 and don't care about it.
                   But we should consider variant, where word is starting
                   with 1. then we get word with length n-1 and k-1 units.
                   So we now have new n = n - k (number of nills is redused by k).
                   And we don't care about positions of units.
**/

int good_binaries (int n, int k)
{
    ASSERT  (n >= k)
    if (n - k == k - 1) return 1;
    if (n - k < k)      return 0;

    if      (k == 0)    return 1;
    else if (k == 1)    return n;
    else                return comb(n - k, k) + comb(n - 1 - (k - 1), k - 1);
}




